package com.itheima.leetcode.od.b.graph;

import java.util.*;

/**
 * <h3>数组排列求和</h3>
 * 1到n的n个连续的数字组成一个数组，n为3的倍数。
 * <p>
 * 每次按顺序从数组中取出3个元素，去掉这3个元素中的一个最大值和一个最小值，并将剩下的元素累计为S，S初始值为0。
 * <p>
 * 可以通过调整数组中元素的位置改变最终结果，每移动一个元素计为移动一次。
 * <p>
 * 请计算最少移动几次可以使得数组和S最大。
 * <p>
 * 输入描述：
 * <p>
 * 数组长度n的范围为[3, 600]
 * <p>
 * 数组中数字范围[1, 10000]
 * <p>
 * 数组由一个字符串表示，不同数字元素之间使用空格分隔
 * <p>
 * 输出描述：
 * <p>
 * 移动次数是一个自然数
 * <p>
 * 无需移动，返回0
 * <p>
 * 示例1：
 * <p>
 * 输入
 * <p>
 * 1 2 3
 * <p>
 * 输出
 * 0
 * <p>
 * 说明
 * 只有一个三元组[1,2,3]，去掉最大最小值后剩下2，S=2。无需移动。
 * <p>
 * 示例2
 * <p>
 * 输入
 * <p>
 * 3 8 9 7 4 2 5 6 1
 * <p>
 * 输出
 * 1
 * <p>
 * 说明：
 * <p>
 * 8+4+5=17
 * <p>
 * 三个三元组：389->8，742->4，561->5，对应的S值为8+4+5=17
 * <p>
 * 将7移动到56之间,三元组调整结果为389， 425， 761
 * <p>
 * 389->8，425->4，761->6，8+4+6=18,18 是所有排列中的最大值，输出 1
 */
public class BFSArrayPermutationSum {
    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();*/
        String input = "3 8 9 7 4 2 5 6 1";
        System.out.println(solve(input));
    }

    public static String solve(String string) {
        int[] arr = Arrays.stream(string.split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = arr.length;

        // 计算理论最大S值 等差数组求和公式 n-1 n-3 ... n-1-2*(n/3-1)
        // 举个例子 1到9，1最小怎么放绝对不是中间值，9最大也无论怎么放绝对不是中间值，所以 最大的组合是 8 6 4
        // 最大值是个定数，所以问题的答案可以理解为最少多少步达到最大值
        int sMax = (2 * n * n) / 9;

        // 初始化BFS队列和访问集合
        LinkedList<Object[]> queue = new LinkedList<>();

        Set<Long> visited = new HashSet<>();
        long initialHash = hashArray(arr);
        queue.offer(new Object[]{arr, 0});
        visited.add(initialHash);

        // BFS层级广度遍历
        while (!queue.isEmpty()) {

            LinkedList<Object[]> newQueue = new LinkedList<>();

            while (!queue.isEmpty()) {
                Object[] current = queue.poll();
                int[] currentArr = (int[]) current[0];
                int moves = (int) current[1];

                // 检查当前状态是否达到最大S值
                if (calculateSValue(currentArr) == sMax) {
                    return String.valueOf(moves);
                }
                // 获取当前状态的所有一步移动结果
                int[] tempArr = Arrays.copyOf(currentArr, n);
                for (int i = 0; i < n; i++) {
                    int element = currentArr[i];

                    for (int j = 0; j < n; j++) {
                        if (i == j) {
                            continue;
                        }

                        // 移动元素
                        System.arraycopy(currentArr, 0, tempArr, 0, n);
                        if (i < j) {
                            System.arraycopy(tempArr, i + 1, tempArr, i, j - i);
                            tempArr[j] = element;
                        } else {
                            System.arraycopy(tempArr, j, tempArr, j + 1, i - j);
                            tempArr[j] = element;
                        }

                        // 检查新状态
                        long hash = hashArray(tempArr);
                        if (!visited.contains(hash)) {
                            visited.add(hash);
                            newQueue.offer(new Object[]{Arrays.copyOf(tempArr, n), moves + 1});
                        }
                    }
                }

                queue = newQueue;
            }
        }

        return "-1";
    }

    /**
     * 计算数组的S值
     * 优化：直接使用数组，避免创建额外的List
     * 优化：使用预计算的最大最小值位置
     *
     * @param arr
     * @return
     */
    public static int calculateSValue(int[] arr) {
        int totalS = 0;
        for (int i = 0; i < arr.length; i += 3) {
            // 只需要三个数中的中间值
            totalS += getMiddle(arr[i], arr[i + 1], arr[i + 2]);
        }
        return totalS;
    }

    /**
     * 获取三个数中的中间值
     * 优化：使用位运算和数学函数
     *
     * @param a
     * @param b
     * @param c
     * @return
     */
    private static int getMiddle(int a, int b, int c) {
        return a + b + c - Math.max(Math.max(a, b), c) - Math.min(Math.min(a, b), c);
    }

    /**
     * 计算数组的哈希值
     * 优化：使用更快的哈希算法
     *
     * @param arr
     * @return
     */
    private static long hashArray(int[] arr) {
        long hash = 1;
        for (int i = 0; i < arr.length; i++) {
            hash = hash * 31 + arr[i];
        }
        return hash;
    }
}